/* eslint-disable no-param-reassign */
/* eslint-disable class-methods-use-this */

import { BinaryTreeNode } from './binaryTreeNode'

/**
 * 二叉查找树
 * 性质：
 * 1. 左结点的关键字小于当前结点的关键字
 * 2. 右结点的关键字大于当前结点的关键字
 */
export class BinarySearchTree<K, V> {
	root: BinaryTreeNode<K, V>

	delete(node: BinaryTreeNode<K, V>): BinaryTreeNode<K, V> {
		let y: BinaryTreeNode<K, V>
		let x: BinaryTreeNode<K, V>
		if (node.leftChild === undefined || node.rightChild === undefined) {
			y = node
		} else {
			y = this.successor(node)
		}

		if (y.leftChild !== undefined) {
			x = y.leftChild
		} else {
			x = y.rightChild
		}

		if (x !== undefined) {
			x.parent = y.parent
		}

		if (y.parent === undefined) {
			this.root = x
		} else if (y.parent.leftChild === y) {
			y.parent.leftChild = x
		} else {
			y.parent.rightChild = x
		}

		if (y !== node) {
			y.copyAttributesTo(node)
		}

		return y
	}

	insert(key: K, value: V): void {
		let y: BinaryTreeNode<K, V>
		let x = this.root
		while (x !== undefined) {
			y = x
			if (key < x.key) {
				x = x.leftChild
			} else {
				x = x.rightChild
			}
		}

		const node = new BinaryTreeNode<K, V>(key, value)
		node.parent = y
		if (y === undefined) {
			this.root = node
		} else if (node.key < y.key) {
			y.leftChild = node
		} else {
			y.rightChild = node
		}
	}

	maximum(node?: BinaryTreeNode<K, V>): BinaryTreeNode<K, V> {
		let nodeX = node === undefined ? this.root : node
		if (nodeX === undefined) {
			return nodeX
		}

		while (nodeX.rightChild !== undefined) {
			nodeX = nodeX.rightChild
		}

		return nodeX
	}

	minimum(node?: BinaryTreeNode<K, V>): BinaryTreeNode<K, V> {
		let nodeX = node === undefined ? this.root : node
		if (nodeX === undefined) {
			return nodeX
		}

		while (nodeX.leftChild !== undefined) {
			nodeX = nodeX.leftChild
		}

		return nodeX
	}

	/**
	 * 返回指定结点在中序遍历中的前趋结点
	 * @param _node the node
	 */
	predecessor(_node: BinaryTreeNode<K, V>): BinaryTreeNode<K, V> {
		// TODO
		throw new Error('Not implemented')
	}

	/**
	 * Search 的非递归版本
	 * @param key the key
	 */
	search(key: K): BinaryTreeNode<K, V> {
		let node = this.root
		while (node !== undefined && node.key !== key) {
			if (key < node.key) {
				node = node.leftChild
			} else {
				node = node.rightChild
			}
		}

		return node
	}

	/**
	 * 返回指定结点在中序遍历中的后继结点
	 * @param node the node
	 */
	successor(node: BinaryTreeNode<K, V>): BinaryTreeNode<K, V> {
		if (node.rightChild !== undefined) {
			return this.minimum(node.rightChild)
		}

		let y = node.parent
		while (y !== undefined && node === y.rightChild) {
			node = y
			y = y.parent
		}

		return y
	}

	walkInorder(
		node: BinaryTreeNode<K, V>,
		callback: (node: BinaryTreeNode<K, V>) => void
	): void {
		if (node.leftChild !== undefined) {
			this.walkInorder(node.leftChild, callback)
		}
		callback(node)
		if (node.rightChild !== undefined) {
			this.walkInorder(node.rightChild, callback)
		}
	}

	walkPostorder(
		node: BinaryTreeNode<K, V>,
		callback: (node: BinaryTreeNode<K, V>) => void
	): void {
		if (node.leftChild !== undefined) {
			this.walkPostorder(node.leftChild, callback)
		}
		if (node.rightChild !== undefined) {
			this.walkPostorder(node.rightChild, callback)
		}
		callback(node)
	}

	walkPreorder(
		node: BinaryTreeNode<K, V>,
		callback: (node: BinaryTreeNode<K, V>) => void
	): void {
		callback(node)
		if (node.leftChild !== undefined) {
			this.walkPreorder(node.leftChild, callback)
		}
		if (node.rightChild !== undefined) {
			this.walkPreorder(node.rightChild, callback)
		}
	}
}
